using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0837. 新21点")]
    public class No0837_New21Game : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(New21Game,
                10, 1, 10,
                equalsMethod: (d1, d2) => (d1).ToFixed(2) == d2.ToFixed(2),
                1.00);

            Assert.TestExe(New21Game,
                6, 1, 10,
                equalsMethod: (d1, d2) => (d1).ToFixed(2) == d2.ToFixed(2),
                0.60);

            Assert.TestExe(New21Game,
                21, 17, 10,
                equalsMethod: (d1, d2) => (d1).ToFixed(2) == d2.ToFixed(2),
                0.73278);
        }

        public double New21Game(int N, int K, int W)
        {
            if (K == 0)
            {
                return 1.0;
            }
            double[] dp = new double[K + W + 1];
            for (int i = K; i <= N && i < K + W; i++)
            {
                dp[i] = 1.0;
            }
            dp[K - 1] = 1.0 * Math.Min(N - K + 1, W) / W;
            for (int i = K - 2; i >= 0; i--)
            {
                dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
            }
            return dp[0];
        }
    }
}
